from treenode import TreeNode, list_to_tree, TreeToList, midorder_dg


def is_subtree(s, t):
    ttl = TreeToList()
    stack = [s]
    while stack:
        s = stack.pop()
        if s:
            if s.val == t.val and ttl.run(s) == ttl.run(t):
                return True
            stack.append(s.right)
            stack.append(s.left)
    return False


def is_subtree2(s, t):
    return str(t) in str(s)


class Solution3:
    """双递归"""
    def isSameTree(self, a, b):
        if a is None and b is None:
            return True
        if a is None or b is None:
            return False
        return a.val == b.val and self.isSameTree(a.left, b.left) and self.isSameTree(a.right, b.right)

    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if s is None:
            return False
        if self.isSameTree(s, t):
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)


if __name__ == '__main__':
    s = list_to_tree([3, 4, 5, 1, 2])
    # midorder_dg(s)
    t = list_to_tree([4, 1, 2])
    # midorder_dg(t)
    print(preorder_dd(s, t))
